home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / LIST.H < prev    next >
C/C++ Source or Header  |  1992-08-21  |  21KB  |  521 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MJF 03/27/89 -- Initial design and implementation.
  13. // Updated: MJF 04/15/89 -- Added a Base List class.
  14. // Updated: MJF 06/01/89 -- Added const to member function arguments.
  15. // Updated: MJF 06/21/89 -- Changed return types from List& to void or Boolean.
  16. // Updated: MJF 08/10/89 -- Changed return values of methods to List reference
  17. // Updated: MBN 08/20/89 -- Changed template usage to reflect new syntax
  18. // Updated: LGO 10/02/89 -- Fix reference count bug in insert_after_node
  19. // Updated: LGO 10/02/89 -- Set reference count to 1 in node constructor and
  20. //                          eliminate many reference method calls.
  21. // Updated: MBN 10/11/89 -- Change "current_position" to "curpos" and also
  22. //                          "previous_position" to "prevpos"
  23. // Updated: LGO 10/18/89 -- Get rid of the sort_test method
  24. // Updated: LGO 10/18/89 -- Simplify the value method to avoid yacc stack oflow
  25. // Updated: MBN 10/19/89 -- Added optional argument to set_compare method
  26. // Updated: MBN 10/19/89 -- Added optional starting position to find method
  27. // Updated: MBN 02/14/90 -- Make push return FALSE if out of heap memory
  28. // Updated: VDN 02/21/92 -- New lite version and plug all memory leaks
  29. // Updated: JAM 08/14/92 -- removed DOS specifics, stdized #includes
  30. // Updated: JAM 08/14/92 -- modernized template syntax, remove macro hacks
  31. //                          non-template classes Cool_List=>CoolBase_List
  32. //                          CoolList_Node=>CoolBase_List_Node
  33. // Updated: JAM 08/14/92 -- consistent use of const void* like in Base_List
  34. // Updated: JAM 08/20/92 -- made *_state typedef a nested typedef "IterState"
  35. //                          as per new Iterator convention
  36. //
  37. // A list is simply  made up  of a  collection of nodes.   Each node contains a
  38. // reference count, a  pointer to  the next node  in  the  list, and the   data
  39. // object.  An overview of the structure of  the  List class, along with  a
  40. // synopsis of each member and friend function, can be found in the Base_List.h
  41. // header file.
  42. //
  43. //
  44. //                      +--------+         +--------+         +--------+
  45. //                      | Ref=2  |         | Ref=1  |         | Ref=2  |
  46. //    +---------+       +--------+         +--------+         +--------+
  47. //    |  List --+-+---->| Next --+-------->| Next --+----+--->| Next 0 |
  48. //    +---------+ |     +--------+         +--------+    |    +--------+
  49. //                |     | Data   |         | Data   |    |    | Data   |
  50. //                |     +--------+         +--------+    |    +--------+
  51. //                |                                      |
  52. //    +---------+ |                          +---------+ |
  53. //    |  List --+-+                          |  List --+-+
  54. //    +---------+                            +---------+
  55. //
  56.  
  57. #ifndef LISTH                    // If LIST not yet defined,
  58. #define LISTH                    // indicate class List done
  59.  
  60. #include <stdarg.h>                // for variable arglists
  61.  
  62. #ifndef BASE_LISTH                // If Base LIST not defined,
  63. #include <cool/Base_List.h>            // include Base_List header
  64. #endif
  65.  
  66.  
  67. template <class Type> 
  68. class CoolList_Node : public CoolBase_List_Node {
  69. friend class CoolList<Type>;
  70. public:
  71.   CoolList_Node(CoolList_Node<Type>&);    // Copy constructor
  72.   CoolList_Node(const Type& head, CoolList_Node<Type>* tail);
  73.   virtual const void* get_data();            // Returns data element 
  74.   virtual void  set_data(const void*);        // Set data element
  75.  
  76. protected:
  77.   Type data;                    // Data of node
  78.   virtual ~CoolList_Node();        // Destructor is virtual
  79. };
  80.  
  81. template <class Type>
  82. class CoolList : public CoolBase_List {
  83. public:
  84.   CoolList();                // List<int> l;  a nil list.
  85.   CoolList(int n, Type head, ...);    // List<int> l4 = (3,11,22,33);
  86.   CoolList(const Type& head);        // List<String> l1 = "333";
  87.   CoolList(const Type& head, CoolList<Type>& tail); //List<String>l2 = ("a", l1);
  88.   CoolList(CoolList<Type>& tail);              // Copy constructor
  89.  
  90.   virtual ~CoolList();            // Destructor is virtual
  91.   
  92.   inline Type& value();                // Value at current position
  93.   int position();                // Current position index
  94.   
  95.   void set_compare(Boolean (*cf)(const Type&, const Type&) = 0); // Sets Compare
  96.   inline CoolList<Type>& operator=(const CoolList<Type>& l);  // list1 = list2;
  97.   
  98.   Type& operator[](int n);            // x = l[n];
  99.   inline Type& get(int n = 0);            // Returns nth data-node
  100.   Boolean put(const Type& x, int n = 0);    // Sets nth data-node to x
  101.   
  102.   inline int position(const Type& x);        // Returns zero-relative index 
  103.   inline IterState& current_position ();    // Set/Get current position
  104.   inline Boolean find(const Type& x, IterState s = NULL); // True if contains x
  105.   
  106.   // returns true if THIS list contains element x and 
  107.   // sets list l to a sublist in THIS list starting at first occurrence of x
  108.   inline Boolean member(CoolList<Type>& l, const Type& x);
  109.   
  110.   Boolean push(const Type& x);            // Adds x to head of this list
  111.   inline Boolean push_new(const Type& x);    // Push if not already member
  112.   inline Boolean push_end(const Type& x);    // Adds x at end of this list
  113.   inline Boolean push_end_new(const Type& x);    // Push_end(x) if not member
  114.   
  115.   Boolean pop(Type& result);            // Removes head/returns data
  116.   Type pop();                    // Removes head/returns data
  117.   
  118.   Type remove();                // Remove/return curpos
  119.   inline Boolean remove(const Type& x);        // Removes first occurrence
  120.   
  121.   inline Boolean replace(const Type& old_data, const Type& new_data); 
  122.   inline Boolean replace_all(const Type& old_data, const Type& new_data); 
  123.   
  124.   inline void sort(Boolean (*f)(const Type&, const Type&)); // Sort list using predicate
  125.   inline void merge(const CoolList<Type>& l, Boolean (*f)(const Type&, const Type&)); // Merge
  126.   
  127.   inline Boolean insert_before(const Type& new_item); // Insert item before
  128.   inline Boolean insert_after(const Type& new_item);  // Insert item after
  129.   
  130.   inline Boolean insert_before(const Type& new_item, const Type& targ_item);
  131.   inline Boolean insert_after(const Type& new_item, const Type& targ_item);
  132.   
  133.   inline CoolList<Type>& operator&=(const CoolList<Type>& l); // Intersection/assign
  134.   inline CoolList<Type>& operator|=(const CoolList<Type>& l); // Union/assign
  135.   inline CoolList<Type>& operator-=(const CoolList<Type>& l); // Difference/assign
  136.   inline CoolList<Type>& operator^=(const CoolList<Type>& l); // XOR/assign
  137.   inline CoolList<Type>& operator+=(const CoolList<Type>& l); // Concatenation/assign
  138.   
  139.   inline CoolList<Type> operator&(const CoolList<Type>& l); // Intersection
  140.   inline CoolList<Type> operator|(const CoolList<Type>& l); // Union
  141.   inline CoolList<Type> operator-(const CoolList<Type>& l); // Difference
  142.   inline CoolList<Type> operator^(const CoolList<Type>& l); // XOR
  143.   inline CoolList<Type> operator+(const CoolList<Type>& l); // Concatenation
  144.  
  145. private:
  146.   static Boolean (*compare_s)(const Type&, const Type&);    // Function used by == test
  147.   friend Boolean CoolList_is_data_equal(const Type& a, const Type& b); // a==b
  148.   
  149.   CoolList(CoolList_Node<Type>*);        // Internal-use constructor
  150.   virtual CoolBase_List* new_list(CoolBase_List_Node*);    // Creates a new list from node
  151.   
  152.   virtual CoolBase_List_Node* insert_before_node(const void* v, CoolBase_List_Node* next_np);
  153.   virtual CoolBase_List_Node* insert_after_node(const void* v, CoolBase_List_Node* prev_np) const;
  154.   
  155.   virtual Boolean compare_data(const void*, const void*) const;
  156.   virtual Boolean do_find(CoolBase_List_Node* np, const void* x,
  157.               CoolBase_List_Node*& cp, CoolBase_List_Node*& pp) const;
  158.   
  159.   virtual void output_data(ostream&, const CoolBase_List_Node*) const;
  160. };
  161.  
  162.  
  163. // value() -- Returns value at current position.
  164. // Input:     None.
  165. // Output:    A Type reference of data at current position.
  166.  
  167. template <class Type> 
  168. inline Type& CoolList<Type>::value() {
  169. #ifdef ERROR_CHECKING  
  170.   if (CoolBase_List::curpos == NULL)
  171.     this->value_error (#Type);            // Raise exception
  172. #endif
  173.   return ((CoolList_Node<Type>*) CoolBase_List::curpos)->data;
  174. }
  175.  
  176. // position -- Return current position.
  177. // Input:      THIS.
  178. // Output:     An integer representing current position.
  179.  
  180. template <class Type> 
  181. inline int CoolList<Type>::position() {
  182.   return CoolBase_List::position();            // can inherit only if has
  183. }
  184.  
  185.  
  186. // operator=() -- Assigns THIS to the specified list.
  187. // Input:         A reference to a list which THIS will be assigned to.
  188. // Output:        A reference to THIS.
  189.  
  190. template <class Type> 
  191. inline CoolList<Type>& CoolList<Type>::operator=(const CoolList<Type>& l) {
  192.   if (this != &l) 
  193.     CoolBase_List::operator=(l);
  194.   return *this;
  195. }
  196.  
  197.  
  198. // get() -- Returns the nth node of THIS. With no arguments, returns first node
  199. // Input:   A positive integer index (default 0).
  200. // Output:  A Type reference of data in the nth node of THIS.
  201.  
  202. template <class Type> 
  203. inline Type& CoolList<Type>::get(int n) {
  204. #if ERROR_CHECKING
  205.   if (n < 0)
  206.     this->get_error (#Type, n);
  207. #endif
  208.   return operator[](n);
  209. }
  210.  
  211.  
  212.  
  213. // position() -- Returns the position of the specified data item in this list.
  214. //               If item not in list, returns -1
  215. // Input:        A Type reference to a data item.
  216. // Output:       The integer position.
  217.  
  218. template <class Type> 
  219. inline int CoolList<Type>::position(const Type& x) {
  220.   return CoolBase_List::position((const void*)&x);
  221. }
  222.  
  223. // current_position () -- Return current position state
  224. // Input:                 None
  225. // Output:                Reference to current position state
  226.  
  227. template <class Type> 
  228. inline /*CoolList<Type>::IterState##*/CoolBase_List_Node*& CoolList<Type>::current_position () {
  229.   return this->curpos;
  230. }
  231.  
  232.  
  233. // find() -- Returns TRUE if the specified element is a member of THIS list.
  234. // Input:    A Type reference to data item to be searched.
  235. // Output:   TRUE or FALSE.
  236.  
  237. template <class Type> 
  238. inline Boolean CoolList<Type>::find(const Type& x, /*CoolList<Type>::IterState##*/CoolBase_List_Node* s) {
  239.   if (s == NULL)                // If no starting position?
  240.     s = this->node_ptr;                // Start at head of list
  241.   return this->do_find(s, &x, this->curpos, this->prevpos); // Find and return
  242. }
  243.  
  244.  
  245. // member() -- Returns the tail of THIS list beginning with the first
  246. //             occurrence of the specified data item.
  247. // Input:      A Type reference to data item to be searched.
  248. // Output:     A list reference of some tail of THIS.
  249.  
  250. template <class Type> 
  251. inline Boolean CoolList<Type>::member(CoolList<Type>& l, const Type& x) {
  252.   return CoolBase_List::member(l, (const void*)&x);
  253. }
  254.  
  255.  
  256.  
  257. // push_new() -- Pushes the specified data item at front of this list if it is
  258. //               not already a member 
  259. // Input:        A reference to a new Type.
  260.   // Output:       TRUE if item not on list, FALSE otherwise.
  261.  
  262. template <class Type> 
  263. inline Boolean CoolList<Type>::push_new(const Type& x) {
  264.   return CoolBase_List::push_new((const void*)&x);
  265. }
  266.  
  267.  
  268. // push_end() -- Appends the specified data item to the end of this list
  269. // Input:        A Type reference to the data item to be appended.
  270. // Output:       TRUE.
  271.  
  272. template <class Type> 
  273. inline Boolean CoolList<Type>::push_end(const Type& x) {
  274.   return CoolBase_List::push_end((const void*)&x);
  275. }
  276.  
  277.  
  278. // push_end_new() -- Appends the specified data item to the end of THIS list
  279. //                   if not already a member 
  280. // Input:            A Type reference to the data item to be appended.
  281. // Output:           TRUE if item not on list, FALSE otherwise.
  282.  
  283. template <class Type> 
  284. inline Boolean CoolList<Type>::push_end_new(const Type& x) {
  285.   return CoolBase_List::push_end_new((const void*)&x);
  286. }
  287.  
  288.  
  289. // remove() -- Removes the first occurrence of the specified item in this list
  290. // Input:      A refernce to data item to be removed.
  291. // Output:     TRUE if item found and removed, FALSE otherwise.
  292.  
  293. template <class Type> 
  294. inline Boolean CoolList<Type>::remove(const Type& x) {
  295.   return CoolBase_List::remove((const void*)&x);
  296. }
  297.  
  298.  
  299. // replace() -- Replaces the first occurrence of specified data item in THIS
  300. //              list with a new value
  301. // Input:       A reference to the data item to be replaced and the new value.
  302. // Output:      TRUE if item found and replaced, FALSE otherwise.
  303.  
  304. template <class Type> 
  305. inline Boolean CoolList<Type>::replace(const Type& old_data, const Type& new_data) {
  306.   return CoolBase_List::replace((const void*)&old_data, (const void*)&new_data);
  307. }
  308.  
  309.  
  310. // replace_all() -- Replaces all occurrences of the specified data item in THIS
  311. //                  list with a new value.
  312. // Input:           A reference to the data item to be replaced and new value.
  313. // Output:          TRUE if at least one item found and replaced, else FALSE
  314.  
  315. template <class Type> 
  316. inline Boolean CoolList<Type>::replace_all(const Type& old_d, const Type& new_d) {
  317.   return CoolBase_List::replace_all((const void*)&old_d, (const void*)&new_d);
  318. }
  319.  
  320.  
  321. // sort() -- Sorts the elements of THIS using the specified predicate function.
  322. // Input:    A predicate function pointer.
  323. // Output:   None.
  324.  
  325. template <class Type> 
  326. inline void CoolList<Type>::sort(Boolean (*f)(const Type&, const Type&)) {
  327.   CoolBase_List::sort((Predicate)f);
  328. }
  329.  
  330.  
  331. // merge() -- Merges the elements of list with the elements of the specified
  332. //            list sorted with the specified predicate function
  333. // Input:     A reference to a list to be merged and a predicate function
  334. //            pointer.
  335. // Output:    None.
  336.  
  337. template <class Type> 
  338. inline void CoolList<Type>::merge(const CoolList<Type>& l, Boolean (*f)(const Type&, const Type&)) {
  339.   CoolBase_List::merge(l, (Predicate)f);
  340. }
  341.  
  342.  
  343. // insert_before() -- Inserts the specified item before the current position
  344. // Input:             A Type reference of new item.
  345. // Output:            TRUE if current position is valid, FALSE otherwise.
  346.  
  347. template <class Type> 
  348. inline Boolean CoolList<Type>::insert_before(const Type& new_item) {
  349. #if ERROR_CHECKING
  350.   if (this->curpos == NULL)
  351.     this->before_error (#Type);
  352. #endif
  353.   return CoolBase_List::insert_before((const void*)&new_item);
  354. }
  355.  
  356.  
  357. // insert_after() -- Inserts the specified item after the current position
  358. // Input:            A Type reference of new item.
  359. // Output:           TRUE if current position is valid, FALSE otherwise.
  360.  
  361. template <class Type> 
  362. inline Boolean CoolList<Type>::insert_after(const Type& new_item) {
  363. #if ERROR_CHECKING
  364.   if (this->curpos == NULL)
  365.     this->after_error (#Type);
  366. #endif
  367.   return CoolBase_List::insert_after((const void*)&new_item);
  368. }
  369.  
  370.  
  371. // insert_before() -- Inserts the specified new item before the specified
  372. //                    target item in this list
  373. // Input:             Two data Type references.
  374. // Output:            TRUE if target item found, FALSE otherwise.
  375.  
  376. template <class Type> 
  377. inline Boolean CoolList<Type>::insert_before(const Type& new_item,
  378.                      const Type& target_item) {
  379.   return CoolBase_List::insert_before((const void*)&new_item,(const void*)&target_item);
  380. }
  381.  
  382. // Boolean insert_after(Type&, Type&) -- inserts the specified new item
  383. //                                       after the specified target item
  384. //                                       in THIS list.
  385. //
  386. // Input:   Two data Type references.
  387. // Output:  TRUE if target item found, FALSE otherwise.
  388.  
  389. template <class Type> 
  390. inline Boolean CoolList<Type>::insert_after(const Type& item, const Type& target) {
  391.   return CoolBase_List::insert_after((const void*)&item, (const void*)&target);
  392. }
  393.  
  394.  
  395. // operator&=() -- Intersection of THIS list with the specified list.
  396. // Input:          A reference to the list.
  397. // Output:         A modified THIS.
  398.  
  399. template <class Type> 
  400. inline CoolList<Type>& CoolList<Type>::operator&=(const CoolList<Type>& l) {
  401.   this->set_intersection(l);
  402.   return *this;
  403. }
  404.  
  405.  
  406. // operator|=() -- Union of THIS list with the specified list.
  407. // Input:          A reference to the list.
  408. // Output:         A reference to a new list containing a copy of the elements
  409. //                 of THIS list and the elements of the specified list.
  410.  
  411. template <class Type> 
  412. inline CoolList<Type>& CoolList<Type>::operator|=(const CoolList<Type>& l) {
  413.   this->set_union(l);
  414.   return *this;
  415. }
  416.  
  417.  
  418. // operator-=() -- Difference of THIS list with the specified list.
  419. // Input:          A reference to the list.
  420. // Output:         A modified THIS.
  421.  
  422. template <class Type> 
  423. inline CoolList<Type>& CoolList<Type>::operator-=(const CoolList<Type>& l) {
  424.   this->set_difference(l);
  425.   return *this;
  426. }
  427.  
  428.  
  429. // operator^=() -- Exclusive-or of THIS list with the specified list.
  430. // Input:          A reference to the list.
  431. // Output:         A modified THIS.
  432.  
  433. template <class Type> 
  434. inline CoolList<Type>& CoolList<Type>::operator^=(const CoolList<Type>& l) {
  435.   this->set_xor(l);
  436.   return *this;
  437. }
  438.  
  439.  
  440. // operator+=() -- Concatenates THIS list with the specified list.
  441. // Input:          A reference to the list to be concatenated.
  442. // Output:         A modified THIS.
  443. //
  444.  
  445. template <class Type> 
  446. inline CoolList<Type>& CoolList<Type>::operator+=(const CoolList<Type>& l) {
  447.   this->append(l);
  448.   return *this;
  449. }
  450.  
  451. // operator&() -- Intersection of a copy of THIS list with the specified list
  452. // Input:         A reference to the list.
  453. // Output:        A new list ret. by value containing a copy of the elements
  454. //                of THIS and the elements of the specified list.
  455.  
  456. template <class Type> 
  457. inline CoolList<Type> CoolList<Type>::operator&(const CoolList<Type>& l) {
  458.   CoolList<Type> new_copy;            // temporary deleted on exit
  459.   new_copy.copy(*this);                // copy nodes of this 
  460.   new_copy.set_intersection(l);            // mutate with inters. of l
  461.   return new_copy;                // will copy only list header
  462. }
  463.  
  464.  
  465. // operator|() -- Union of a copy of THIS list with the specified list
  466. // Input:         A reference to the list.
  467. // Output:        A reference to a new list containing a copy of the elements
  468. //                of THIS and the elements of the specified list.
  469.  
  470. template <class Type> 
  471. inline CoolList<Type> CoolList<Type>::operator|(const CoolList<Type>& l) {
  472.   CoolList<Type> new_copy;            // temporary deleted on exit
  473.   new_copy.copy(*this);                // copy nodes of this
  474.   new_copy.set_union(l);            // mutate with union of l
  475.   return new_copy;                // will copy only list header
  476. }
  477.  
  478.  
  479. // operator-() -- Difference of a copy of THIS list with the specified list.
  480. // Input:         A reference to the list.
  481. // Output:        A reference to a new list containing a copy of the elements
  482. //                of THIS and the elements of the specified list.
  483.  
  484. template <class Type> 
  485. inline CoolList<Type> CoolList<Type>::operator-(const CoolList<Type>& l) {
  486.   CoolList<Type> new_copy;            // temporary deleted on exit
  487.   new_copy.copy(*this);                // copy nodes of this 
  488.   new_copy.set_difference(l);            // mutate with diff of l
  489.   return new_copy;                // will copy only list header
  490. }
  491.  
  492.  
  493. // operator^() -- Exclusive-or of a copy of THIS list with the specified list.
  494. // Input:         A reference to the list.
  495. // Output:        A reference to a new list containing a copy of the elements
  496. //                of THIS and the elements of the specified list.
  497.  
  498. template <class Type> 
  499. inline CoolList<Type> CoolList<Type>::operator^(const CoolList<Type>& l) {
  500.   CoolList<Type> new_copy;            // temporary deleted on exit
  501.   new_copy.copy(*this);                // copy nodes of this
  502.   new_copy.set_xor(l);                // mutate with xor of l
  503.   return new_copy;                // will copy only list header
  504. }
  505.  
  506.  
  507. // operator+() -- Concatenates a copy of THIS list with the specified list.
  508. // Input:         A reference to the list to be concatenated.
  509. // Output:        A reference to a new list containing a copy of the elements
  510. //                of THIS and the elements of the specified list.
  511.  
  512. template <class Type> 
  513. inline CoolList<Type> CoolList<Type>::operator+(const CoolList<Type>& l) {
  514.   CoolList<Type> new_copy;            // temporary deleted on exit
  515.   new_copy.copy(*this);                // copy nodes of this 
  516.   new_copy.append(l);                // mutate with concat. of l
  517.   return new_copy;                // will copy only list header
  518. }
  519.  
  520. #endif                // End #ifdef of LISTH
  521.